//给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。 
//
// 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？ 
//
// 
//
// 示例 1： 
//
// 输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
// 
//
// 示例 2： 
//
// 输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 示例 3： 
//
// 输入：nums1 = [0,0], nums2 = [0,0]
//输出：0.00000
// 
//
// 示例 4： 
//
// 输入：nums1 = [], nums2 = [1]
//输出：1.00000
// 
//
// 示例 5： 
//
// 输入：nums1 = [2], nums2 = []
//输出：2.00000
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -106 <= nums1[i], nums2[i] <= 106 
// 
// Related Topics 数组 二分查找 分治算法 
// 👍 3296 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

/**
 * Java：寻找两个正序数组的中位数
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P4_MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        Solution solution = new P4_MedianOfTwoSortedArrays().new Solution();
        int[] nums1 = MyUtil.createArray(1);
        int[] nums2 = MyUtil.createArray(3, 4);
        MyUtil.print(solution.findMedianSortedArrays(nums1, nums2));
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 合并两个数组
     * T O(N+M)
     * S O(N+M)
     */
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            // 合并
            int N = nums1.length + nums2.length;
            int[] nums = new int[N];
            int i = 0, j = 0, index = 0;
            while (i < nums1.length || j < nums2.length) {
                // nums1走完了
                if (i >= nums1.length) {
                    nums[index++] = nums2[j++];
                    continue;
                }
                // nums2走完了
                if (j >= nums2.length) {
                    nums[index++] = nums1[i++];
                    continue;
                }
                // 都没走完，取较小值
                nums[index++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
            }
            // 偶数取中间两个，奇数直接取中间数
            return (N & 1) == 0 ? (nums[N / 2] + nums[N / 2 - 1]) / 2.0 : nums[N / 2];
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}